class Maze {
  row = 0;
  col = 0;
  road = 0;
  wall = 1;
  offset = []
  entryX = 1
  entryY = 0
  outX = 0
  outY = 0
  width = 500
  height = 500
  maze = []
  path = []
  findPath = []
  visited = []
  findVisited = []
  class = ''
  hasFindPath = false
  constructor(row, col, width, height){
    this.row = row
    this.col = col
    this.road = 0
    this.wall = 1
    this.offset = [[-1,0], [0,1], [1,0], [0,-1]]
    this.entryX = 1
    this.entryY = 0
    this.outX = row - 2
    this.outY = col - 1
    this.width = width
    this.height = height
    this.maze = []
    this.path = []
    this.findPath = []
    this.visited = []
    this.findVisited = []
    this.class = Math.random().toFixed(2)
    this.hasFindPath = false
  }
  initMaze () {
    for(var i=0; i<this.row; i++){
      this.maze[i] = new Array(this.col).fill(this.wall)
      this.visited[i] = new Array(this.col).fill(false)
      this.findVisited[i] = new Array(this.col).fill(false)
      this.path[i] = new Array(this.col).fill(null)
      for(var j=0; j<this.col; j++){
        if(i%2===1 && j%2===1){
          this.maze[i][j] = this.road
        }
      }
    }
    this.maze[this.entryX][this.entryY] = this.road
    this.maze[this.outX][this.outY] = this.road
    this.dfs(this.maze, this.entryX, this.entryY)
  }

  dfs (maze, x, y) {
    let queue = new Queue()
    queue.push({ x: x, y: y + 1 })
    this.visited[x][y+1] = true
    while(!queue.empty()){
      let curPos = queue.pop()
      for(let i=0; i<4; i++){
        let newX = curPos.x + this.offset[i][0] * 2
        let newY = curPos.y + this.offset[i][1] * 2
        if(this.isArea(newX, newY) && !this.visited[newX][newY]){
          maze[(newX + curPos.x) / 2][ (newY + curPos.y) / 2] = this.road
          this.visited[newX][newY] = true
          queue.push({ x: newX, y: newY })
        }
      }
    }
    // console.log(maze)
    // console.log(this.visited)
  //   this.initDOM(maze)
    this.dfsPath(maze, this.entryX, this.entryY)
  }

  dfsPath(maze, x, y){
    let stack = [{x:x, y:y}]
    this.findPath = []
    while(stack.length > 0){
      let curPos = stack.pop()
      this.findVisited[curPos.x][curPos.y] = true
      if(curPos.x === this.outX && curPos.y === this.outY){
        this.hasFindPath = true
        this.findPath.unshift([curPos.x, curPos.y])
        let prePos = this.path[curPos.x][curPos.y]
        while (prePos != null) {
          this.findPath.unshift([prePos.x, prePos.y])
          prePos = this.path[prePos.x][prePos.y]
        }
        break
      }
      for(let i=0; i<4; i++){
        let newX = curPos.x + this.offset[i][0]
        let newY = curPos.y + this.offset[i][1]
        if(this.isArea(newX, newY) && !this.findVisited[newX][newY] && maze[newX][newY] === this.road){
          this.path[newX][newY] = { x: curPos.x, y: curPos.y }
          stack.push({x: newX, y: newY})
        }
      }
    }
    // this.initPathDom(this.findPath)
  }
  // initPathDom(path){
  //   for(let i=0; i<path.length; i++){
  //     let changeSpan = document.querySelector(`span[data-index='${path[i][0]}-${path[i][1]}-${this.class}']`)
  //     changeSpan.style.background = 'red'
  //   }
  // }
  // 初始化迷宫DOM
  // initDOM(maze) {
  //   let oDiv = document.createElement('div')
  //   oDiv.style.width = this.width + 'px'
  //   oDiv.style.height = this.height + 'px'
  //   oDiv.style.display = 'flex'
  //   oDiv.className = 'box'
  //   oDiv.style.flexWrap = 'wrap'
  //   oDiv.style.marginBottom = '20px'
  //   for (let i = 0; i < maze.length; i++) {
  //     for (let j = 0; j < maze[i].length; j++) {
  //       let oSpan = document.createElement('span')
  //       oSpan.dataset.index = i + '-' + j + '-' + this.class
  //       oSpan.style.width = (this.width / this.col).toFixed(2) + 'px'
  //       oSpan.style.height = (this.height / this.row).toFixed(2) + 'px'
  //       oSpan.style.background = maze[i][j] === this.wall ? '#185ed1' : '#fff'
  //       oDiv.appendChild(oSpan)
  //     }
  //   }
  //   // 删除类名为box的div，演示三种切换，需要删除元素重新渲染
  //   let box = document.querySelector('.box')
  //   if (box) {
  //     // document.body.removeChild(box)
  //     document.querySelector('.main').removeChild(box)
  //   }
  //   // document.body.appendChild(oDiv)
  //   document.querySelector('.main').appendChild(oDiv)
  // }

  isArea (x,y) {
    return x > 0 && x < this.row - 1 && y > 0 && y < this.col - 1 || x == this.entryX && y == this.entryY || x == this.outX && y == this.outY
  }
}
class Queue {
  queue = []
  constructor(){
      this.queue = []
  }
  push(pos){
      if(Math.random() < 0.5){
      this.queue.push(pos)
      }else{
      this.queue.unshift(pos)
      }
  }
  pop(){
      if(Math.random() < 0.5){
      return this.queue.pop()
      }else{
      return this.queue.shift()
      }
  }
  empty(){
      return !this.queue.length
  }
}